package me.shan.leet.code;

import java.util.Arrays;

/**
 * <a href="https://leetcode.cn/problems/maximum-tastiness-of-candy-basket/">礼盒的最大甜蜜度</a>
 *
 * @author liuchuang
 * @version 1.0
 * @since 2023/6/15 15:44
 */
public class T2517MaximumTastiness {

    public int maximumTastiness(int[] price, int k) {
        Arrays.sort(price);
        int l = 0, r = price[price.length - 1] - price[0];
        int mid = (r + l + 1) / 2;
        while (l < r) {
            if (check(price, mid, k)) {
                l = mid;
            } else {
                r = mid - 1;
            }
            mid = (r + l + 1) / 2;
        }
        return l;
    }

    private boolean check(int[] price, int mid, int k) {
        int prev = Integer.MIN_VALUE / 2;
        int count = 0;
        for (int p : price) {
            if (p - prev >= mid) {
                prev = p;
                count++;
            }
        }
        return count >= k;
    }

    public static void main(String[] args) {
        T2517MaximumTastiness t = new T2517MaximumTastiness();
        System.out.println(t.maximumTastiness(new int[]{7, 7, 7, 7}, 2));
    }
}
